In the field of computer graphics, it is commonplace to render three-dimensional objects in "object space" using a set of polygons. For simplicity, the polygons used are typically triangles, and other polygon shapes are usually broken down into triangles using an available method such as Delauney triangulation. Thus, an object may consist of a set of contiguous triangles each of which is positioned in three-dimensional space relative to the others such that together they form the shape of the desired object. Each of the triangles has a set of Cartesian coordinate values for each of its vertices. These coordinate sets uniquely define the location and orientation of the triangle in three-dimensional space.
Typically, in addition to the Cartesian coordinates, each triangle vertex is also defined by values indicating its surface characteristic, such as texture map coordinates (u,v) for texture mapping, red, green, blue color values (r,g,b,) for Gouraud shading, or vertex normal N (having x,y,z coordinates) for Phong shading. When displaying a three-dimensional object built from triangles, each triangle must first be transformed from the three-dimensional coordinate system to a homogeneous coordinate system. This is typically achieved using a perspective transformation, which results in a homogeneous coordinate value for each of the triangle vertices. That is, the transformation results in each triangle vertex being represented by horizontal and vertical display coordinates (x,y) (the z value is usually also retained for making visibility determinations), as well as the homogeneous coordinate w and surface values, such as texture map coordinates (u,v).
Depending on the application, a triangle may be shaded and/or texture mapped. Whether the shading is Gouraud shading or Phong shading, the shading process is very similar to that of texture mapping, and both contribute to the determination of a color for each pixel within the triangle. In both texture mapping and shading, a value, or values, indicative of pixel color must be assigned to each pixel of the triangle as defined in its homogeneous coordinate system. Typically, this is done by dividing the triangle into horizontal spans, each of which is one pixel width in the vertical direction, determining texture mapping or shading values for the end points of the span, and thereafter the values for the pixels in between. This process is described below for texture mapping, but is similar for the determinations of values for Gouraud or Phong shading.
Shown in FIG. 1 is a triangle 10 having three vertices P.sub.0, P.sub.1, P.sub.2, each of which is uniquely defined by its own set of values (x,y,z,w,u,v). For a given span, such as span 12 shown in the figure, the values for each of the pixels in the span must then be determined. Each pixel is defined by its three-dimensional Cartesian coordinates (x,y,z), and by its value w found from the perspective transformation. However, the values of u and v needed for texture mapping must thereafter be calculated using w. This calculation process makes use of the values at the ends of the span containing the pixel, and very similar calculations would be used to determine r, g, b, or N for shading operations.
Referring again to FIG. 1, if vertex P.sub.0 is defined by the values (x.sub.0, y.sub.0, z.sub.0, w.sub.0, u.sub.0, v.sub.0), and vertex P.sub.1 is defined by the values (x.sub.1, y.sub.1, z.sub.1, w.sub.1, u.sub.1, v.sub.1), the desired values for endpoint P.sub.3 of span 12 may be found from the values for P.sub.0 and P.sub.1. P.sub.3 has Cartesian coordinates x.sub.3 and y.sub.3, and homogeneous coordinate w.sub.3 may be determined as follows: EQU w.sub.3 =(1-t)w.sub.0 +tw.sub.1
the value of u.sub.3 for P.sub.3 may be calculated as follows: EQU u.sub.3 =((1-t)u.sub.0 /w.sub.0 +tu.sub.1 /w.sub.1)/((1-t)/w.sub.0 +t/w.sub.1)
where t is a normalized position value (i.e., from 0 to 1) between P.sub.0 and P.sub.1, such that t=0 at P.sub.0 and t=1 at P.sub.1. Similarly, the value of v.sub.3 for endpoint P.sub.3 may be calculated as: EQU v.sub.3 =((1-t)v.sub.0 /w.sub.0 +tv.sub.1 /w.sub.1)/((1-t)/w.sub.0 +t/w.sub.1)
As with endpoint P.sub.3, the values of u.sub.4 and v.sub.4 for endpoint P.sub.4 may be calculated from the values defining vertex P.sub.1 and those defining vertex P.sub.2 (i.e., x.sub.2, y.sub.2, z.sub.2, w.sub.2, u.sub.2, v.sub.2), since a line segment containing P.sub.4 extends between P.sub.1 and P.sub.2.
The values of u and v for points along a span, such as span 12 of FIG. 1, can be determined using the above equations relative to the values of u, v, w at the endpoints. Thus, for point P.sub.5, located on span 12, the following calculations may be made: EQU u.sub.5 =((1-t)u.sub.3 /w.sub.3 +tu.sub.4 /w.sub.4)/((1-t)/w.sub.3 +t/w.sub.4)
and, EQU v.sub.5 =((1-t)v.sub.3 /w.sub.3 +tv.sub.4 /w.sub.4)/((1-t)/w.sub.3 +t/w.sub.4).
In this manner, the u and v values for each pixel of each span may be found, until mapping for all of the pixels of the triangle is complete.
While performing the above calculations for each of the triangles of the object is the most accurate way to provide it with surface detail, it also typically requires a large number of calculations, and therefore results in a heavy processing burden. The largest computing cost of these calculations is performing the division functions. For example, the calculation necessary to determine u.sub.5 requires five separate division functions. Although the values of 1/w.sub.3 and 1/w.sub.4 may be precalculated, this still requires one division function for each pixel of the triangle. Performing these divisions are extremely costly in terms of circuitry and performance.
One way to reduce the number of divisions performed is to replace the above formula for u or v with a linear approximation which assumes that w.sub.0 =w.sub.1. For example, the linear approximation for determining the value u.sub.5 for point P.sub.5 may be expressed as follows: EQU u.sub.5 =(1-t)u.sub.3 +tu.sub.4
A similar linear approximation may be used to determine values for v, r, g, b, or N. The linear approximation requires no division to compute, and is therefore significantly faster to calculate on a digital computer than the exact formula. However, when w.sub.3 and w.sub.4 are not close in value, the approximation is correspondingly inaccurate. As a result, images which use texture mapping or shading that relies on this type of linear approximation tend to have visible artifacts, the severity of which depend on the difference between the values of w for the two endpoints which would otherwise be used for the calculation.
U.S. Pat. No. 5,594,846 to Donovan discloses a span-based rendering approach which breaks each span into multiple segments, the points separating the segments having a surface characteristic value, such as u, calculated mathematically in the manner described above. The u values for the portions of the span between the calculated points are then determined by interpolation. The calculated points separating the segments are selected so that the segments formed are as long as possible without the error in u resulting from the use of interpolation exceeding a predetermined amount. The Donovan method thereby allows a relatively low number of computations, while keeping errors below a desired threshold. Nonetheless, the span-by-span process of breaking the span into segments requires each new point determined on each span to be calculated using at least one division operation.